package club.westudy.java.demo401;


/**
 * 迷宫游戏
 */
public class MazeGame {

    static class Point {
        int x;
        int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public String toString() {
            return x + "," + y;
        }
    }

    static class Position {
        Point point;//位置
        int direction;//1,2,3,4分别表示东，南，西，北

        public Position(Point point, int direction) {
            this.point = point;
            this.direction = direction;
        }
    }

    char[][] map;
    char[][] map0;

    public MazeGame(char[][] map) {
        this.map = map;
        this.map0 = this.map.clone();
        for (int i = 0; i < this.map0.length; i++) {
            this.map0[i] = this.map[i].clone();
        }
    }

    public void footPrint(Point curPos) {
        this.map[curPos.y][curPos.x] = '*';
    }

    public void markDeadPrint(Point curPos) {
        this.map[curPos.y][curPos.x] = 'X';
    }

    public void markPath(Point curPos) {
        this.map0[curPos.y][curPos.x] = 'O';
    }

    public char[][] genSolution() {
        IStack<Position> stack = new ArrayStack2<Position>();
        // 寻找入口
        Point start = findEnterPoint();
        footPrint(start);
        stack.push(new Position(start, 1));
        Position next = nextStep(start, 1);
        // 默认开始是往右走
        do {
            System.out.println("站在" + stack.peek().point.x + "," + stack.peek().point.y + ",正在尝试" + next.point.x + "," + next.point.y);
            //如果下一步可以通行，则把下一步放入栈中记录
            if (isPass(next)) {
                stack.push(next);
                //将当前可通行的位置标记为@
                footPrint(next.point);
                // 如果都是最底部就是找到出口了
                //改变方向
                next = nextStep(stack.peek().point, 1);
            } else {//如果当前路径不能通行
                while (next.direction == 4 && !stack.isEmpty()) {
                    //死路标记
                    markDeadPrint(stack.peek().point);
                    if(next.point.x == start.x && next.point.y == start.y){
                        throw new RuntimeException("没有出口的迷宫");
                    }
                    //当前这个位置没有可通行的方向，只能退出来
                    next = stack.pop();
                }
                //只要方向没尝试完就换个方向继续走
                if (next.direction < 4) {
                    next = nextStep(stack.peek().point, next.direction + 1);
                }
            }
            print(this.map);
        } while (next != null && !stack.isEmpty());

        // 将走过的路径在地图上标记出来
        while (!stack.isEmpty()){
            Position e = stack.pop();
            markPath(e.point);
        }
        return this.map0;
    }

    private Position nextStep(Point curpos, int direction) {
        int y = curpos.y;
        int x = curpos.x;
        switch (direction) {
            case 1://1,2,3,4分别表示东，南，西，北
                if (x + 1 < this.map[0].length) {
                    x++;
                    break;
                }
                //无路可走
                return null;
            case 2:
                if (y + 1 < this.map.length) {
                    y++;
                    break;
                }
                //无路可走
                return null;
            case 3:
                if (x - 1 >= 0) {
                    x--;
                    break;
                }
                //无路可走
                return null;
            case 4:
                if (y - 1 >= 0) {
                    y--;
                    break;
                }
                //无路可走
                return null;
        }
        return new Position(new Point(x, y), direction);
    }

    /**
     * 寻找入口点
     *
     * @return
     */
    private Point findEnterPoint() {
        Point enter = null;
        for (int i = 0; i < this.map.length; i++) {
            char[] line = this.map[i];
            if (i == 0) {
                for (int j = 0; j < line.length; j++) {
                    char c = this.map[i][j];
                    if (c == ' ') {
                        enter = new Point(j, i);
                        break;
                    }
                }
                break;
            }
        }
        return enter;
    }


    /**
     * 当前所在位置是否可以通行
     *
     * @return
     */
    public boolean isPass(Position elemType) {
        return this.map[elemType.point.y][elemType.point.x] == ' ';
    }

    /**
     * 打印答案
     */
    public void print(char[][] map) {
        for (char[] line : map) {
            for (char c : line) {
                System.out.print(' ');
                System.out.print(c);
            }
            System.out.print('\n');
        }
        System.out.print('\n');
    }

    public static void main(String[] args) {
        // y 行号， x 列号
        char[][] map = new char[][]{
//                {'#', ' ', '#', '#'},
//                {'#', ' ', ' ', '#'},
//                {'#', '#', ' ', '#'},

//                {'#', '#', '#', ' ', '#', '#'},
//                {'#', ' ', ' ', ' ', ' ', '#'},
//                {'#', ' ', '#', '#', ' ', '#'},
//                {'#', ' ', ' ', ' ', '#', '#'},
//                {'#', '#', '#', ' ', ' ', '#'},
//                {'#', '#', '#', '#', ' ', '#'},

                {'#', ' ', '#', '#', '#', '#', '#', '#', '#', '#'},
                {'#', ' ', '#', ' ', ' ', ' ', '#', ' ', ' ', '#'},
                {'#', ' ', ' ', ' ', '#', ' ', '#', ' ', '#', '#'},
                {'#', ' ', '#', '#', '#', ' ', ' ', ' ', ' ', '#'},
                {'#', '#', '#', ' ', ' ', ' ', '#', '#', ' ', '#'},
                {'#', ' ', ' ', ' ', '#', '#', '#', '#', ' ', '#'},
                {'#', ' ', '#', ' ', '#', ' ', ' ', ' ', ' ', '#'},
                {'#', ' ', '#', '#', '#', '#', '#', '#', '#', '#'},
                {'#', ' ', '#', ' ', ' ', ' ', '#', ' ', ' ', '#'},
                {'#', ' ', '#', ' ', '#', ' ', '#', ' ', '#', '#'},
                {'#', ' ', ' ', ' ', '#', ' ', ' ', ' ', '#', '#'},
                {'#', '#', '#', '#', '#', ' ', '#', ' ', ' ', '#'},
                {' ', ' ', '#', '#', '#', ' ', '#', '#', ' ', '#'},
                {'#', ' ', ' ', '#', '#', ' ', '#', ' ', ' ', '#'},
                {'#', '#', ' ', '#', '#', '#', ' ', '#', ' ', '#'},
                {'#', '#', ' ', '#', ' ', ' ', ' ', '#', ' ', '#'},
                {'#', ' ', ' ', '#', ' ', '#', ' ', '#', ' ', '#'},
                {'#', '#', ' ', ' ', ' ', '#', ' ', ' ', ' ', '#'},
                {'#', '#', '#', '#', '#', '#', '#', '#', '#', '#'},
        };
        MazeGame game = new MazeGame(map);
        game.print(game.genSolution());
    }
}
